#include <stdlib.h>

#ifndef SHELL_SORT
#define SHELL_SORT

#include "swap.c"

// # Sedgewick增量序列
// # D=9*4^i-9*2^i+1 或 4^(i+2)-3*2^(i+2)+1 , i>=0
// # 稍微变一下形：D=9*(2^(2i)-2^i)+1 或 2^(2i+4)-3*2^(i+2)+1 , i>=0
int *getSedgewickStepArr(int n, int *dLen) {
    int i = 0;
    int length = 50;
    int *arr = (int *)malloc(sizeof(int) * length);
    int cnt = 0;
    // arr[cnt++] = 1;
    while (1) {
        if (cnt >= length) {
            length *= 2;
            arr = (int *)realloc(arr, sizeof(int) * length);
        }
        int tmp = 9 * ((1 << (2 * i)) - (1 << i)) + 1;
        if (tmp <= n) {
            arr[cnt++] = tmp;
        }
        tmp = (1 << (2 * i + 4)) - 3 * (1 << (i + 2)) + 1;
        if (tmp <= n) {
            arr[cnt++] = tmp;
        } else {
            break;
        }
        i++;
    }
    *dLen = cnt;
    return arr;
}

// 希尔排序，插入排序的一种，先将数组分成若干个子序列，分别进行插入排序，
// 然后逐渐缩小子序列的间隔，直到间隔为 1
// 使用 Sedgewick 增量序列, 1, 5, 19, 41, 109, ...
// Sedgewick 增量序列的递推公式为：1, 4^k+3*2^(k-1)+1, 4^(k+1)+3*2^k+1, ...
void shell_Sort(ElementType a[], int length) {
    int sedgewickStepArr[] = {1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929,
        16001, 36289, 64769, 146305, 260609, 587521, 1045505, 2354689, 4188161,
        9427969, 16764929, 37730305, 67084289, 150958081, 268386305, 603906049,
        1073643521};
    int sedgewickStepArrLen = 28;
    int i, j, k, step;
    ElementType tmp;
    // 初始增量不能超出数组长度
    for (k = 0; length > sedgewickStepArr[k]; k++) {
        ;
    }
    for (; k >= 0; k--) {
        step = sedgewickStepArr[k];
        // 插入排序
        for (i = step; i < length; i++) {
            tmp = a[i];
            for (j = i; j >= step && comparator(tmp, a[j - step]) < 0; j -= step) {
                a[j] = a[j - step];
            }
            a[j] = tmp;
        }
    }
}

#endif
